package net.println.kotlin.chapter5.tailrecursive

data class ListNode(val value: Int, var next: ListNode? = null)

tailrec fun findListNode(head: ListNode?, value: Int): ListNode? {//尾递归，tailrec是尾递归优化，可以转换成一般迭代，防止内存溢出
    head ?: return null
    if (head.value == value) return head
    return findListNode(head.next,value)
}

fun main(args: Array<String>) {
    val MAX_NODE_COUNT = 100000
    val head = ListNode(0)
    var p = head
    for (i in 1..MAX_NODE_COUNT) {
        p.next = ListNode(i)
        p = p.next!!
    }

    println(findListNode(head,MAX_NODE_COUNT-2)?.value)
}

fun factorial(n: Long):Long {//不是尾递归
    return n * factorial(n - 1)
}

data class TreeNode(val value: Int) {
    val left:TreeNode? = null
    val right:TreeNode? = null
}

fun findTreeNode(root: TreeNode?,value: Int):TreeNode? {//不是尾递归
    root?:return null
    if (root.value == value) return root
    return findTreeNode(root.left,value)?:return findTreeNode(root.right,value)
}